package 代码题.链表的题目;

/**
 * 复制复杂链表
 *
 * 题目描述：
 *
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
 * 返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 *
 * 数据结构：
 * public class RandomListNode {
 *     int label;                               数据域
 *     RandomListNode next = null;            指向下一个结点
 *     RandomListNode random = null;       指向任意一个节点
 *
 *     RandomListNode(int label) {
 *         this.label = label;
 *     }
 * }
 */
public class CopyComplexList {

    /**
     * 解题思路：
     * 1.遍历链表，复制链表中的每个结点，并将复制的结点插入到该结点的后面
     * a->b->c变成a->a'->b->b'->c->c'
     *
     * 2.为复制结点的random指针赋值
     * 比如a随机指针指向c，那么a'的随机指针指向c'
     *
     * 3.将链表的原始结点与复制结点分割至两个链表，使原始结点构成一个链表，复制结点构成一个链表。
     * a->a'->b->b'->c->c'变成两个链表，一个是a->b->c，另一个是a'->b'->c'
     */
    public static void main(String[]args) {
        RandomListNode head = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);
        RandomListNode node5 = new RandomListNode(5);
        head.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        head.random = node3;
        node2.random = node5;
        node4.random = node2;
        CopyComplexList s = new CopyComplexList();
        RandomListNode copyList = s.Clone(head);
        while (copyList != null) {
            System.out.print(copyList.label + " ");
            copyList = copyList.next;
        }
        System.out.println();
    }

    //复制复杂链表
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead==null){
            return null;
        }
        copyNodes(pHead);
        initRandom(pHead);
        return split2list(pHead);
    }

    //1.加入copy结点
    public void copyNodes(RandomListNode pHead){
        RandomListNode walkNode=pHead;
        while(walkNode!=null){
            RandomListNode cloneNode=new RandomListNode(walkNode.label);
            cloneNode.next=walkNode.next;
            walkNode.next=cloneNode;
            walkNode=cloneNode.next;
        }
    }

    //2.为新copy结点的random域指定值
    public void initRandom(RandomListNode pHead){
        RandomListNode walkNode=pHead;
        RandomListNode cwalkNode=pHead;
        while(walkNode!=null){
            cwalkNode=walkNode.next;
            if(walkNode.random!=null){
                cwalkNode.random=walkNode.random.next;
            }
            walkNode=cwalkNode.next;
        }
    }

    //3.将链表和其copy版本分为两个链表
    //具体操作是新链表和旧链表 轮流作为支点
    public RandomListNode split2list(RandomListNode pHead){
        RandomListNode cpHead=pHead.next;
        RandomListNode walkNode=pHead;
        RandomListNode cwalkNode=cpHead;
        while(walkNode!=null){
            walkNode.next=cwalkNode.next;
            walkNode=walkNode.next;
            if(walkNode==null){
                cwalkNode.next=null;
            }
            else{
                cwalkNode.next=walkNode.next;
                cwalkNode=cwalkNode.next;
            }
        }
        return cpHead;
    }

}

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}
